백준 1043번
오늘 풀어본 문제는 백준의 1043번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 $N$ 이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 $N$ 과 파티의 수 $M$ 이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 $1$ 부터 $N$ 까지의 수로 주어진다.
셋째 줄부터 $M$ 개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
$N$, $M$ 은 $50$ 이하의 자연수이고, 진실을 아는 사람의 수는 $0$ 이상 $50$ 이하의 정수, 각 파티마다 오는 사람의 수는 $1$ 이상 $50$ 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이과정
1번째 시도
이 문제는 분리 집합 자료구조를 이용하여 해결할 수 있는 문제이다. 분리 집합을 이용하여 사람들이 오는 파티의 인물들을 연결하여 ‘거짓말 해도 되는 그룹’ 과 ‘거짓말 하면 안되는 그룹’ 으로 구분한 뒤, 각 파티의 인물정보를 재확인하는 방식으로 문제를 해결할 수 있다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include "disjoint_set.hpp"
using namespace std;
queue<vector<int>> q;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M, truthKnowers, truthGroup = -1;
cin >> N >> M;
DisjointSet diset(N);
cin >> truthKnowers;
for (int i = 0; i < truthKnowers; i++) {
int tempPerson;
cin >> tempPerson;
tempPerson--;
if (truthGroup == -1) {
truthGroup = tempPerson;
}
else {
diset.merge(tempPerson, truthGroup);
}
}
for (int i = 0; i < M; i++) {
int peopleCount, leader = -1;
cin >> peopleCount;
vector<int> tempVector;
tempVector.emplace_back(peopleCount);
for (int j = 0; j < peopleCount; j++) {
int tempPerson;
cin >> tempPerson;
tempPerson--;
tempVector.emplace_back(tempPerson);
if (leader == -1) {
leader = tempPerson;
}
else {
diset.merge(leader, tempPerson);
}
}
q.push(tempVector);
}
int answer = 0;
while (!q.empty()) {
vector<int> party = q.front();
q.pop();
answer++;
for (int i = 1; i <= party[0]; i++) {
if (truthGroup != -1 && diset.find(truthGroup) == diset.find(party[i])) {
answer--;
break;
}
}
}
cout << answer;
return 0;
}
실행 결과 ‘컴파일 에러’가 나왔다.
2번째 시도
코드를 자세히 읽어보았다면 눈치챘겠지만, DisjointSet 클래스를 다른 파일에 구현하고 그 파일을 include 하는 방식으로 코드를 작성해버렸다.
평소에는 코드를 완성하고 나면 구현해둔 파일에서 자료구조를 복사하여 원래 코드에 붙여넣어서 제대로 제출해왔지만, 오늘은 깜빡하고 코드를 그냥 제출해버린 것이다.
코드를 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
private:
std::vector<int> parent;
std::vector<int> rank;
public:
DisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int u) {
if (u == parent[u]) {
return u;
}
else {
return parent[u] = find(parent[u]);
}
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
if (rank[u] > rank[v]) {
std::swap(u, v);
}
parent[u] = v;
if (rank[u] == rank[v]) {
rank[v]++;
}
}
}
};
queue<vector<int>> q;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M, truthKnowers, truthGroup = -1;
cin >> N >> M;
DisjointSet diset(N);
cin >> truthKnowers;
for (int i = 0; i < truthKnowers; i++) {
int tempPerson;
cin >> tempPerson;
tempPerson--;
if (truthGroup == -1) {
truthGroup = tempPerson;
}
else {
diset.merge(tempPerson, truthGroup);
}
}
for (int i = 0; i < M; i++) {
int peopleCount, leader = -1;
cin >> peopleCount;
vector<int> tempVector;
tempVector.emplace_back(peopleCount);
for (int j = 0; j < peopleCount; j++) {
int tempPerson;
cin >> tempPerson;
tempPerson--;
tempVector.emplace_back(tempPerson);
if (leader == -1) {
leader = tempPerson;
}
else {
diset.merge(leader, tempPerson);
}
}
q.push(tempVector);
}
int answer = 0;
while (!q.empty()) {
vector<int> party = q.front();
q.pop();
answer++;
for (int i = 1; i <= party[0]; i++) {
if (truthGroup != -1 && diset.find(truthGroup) == diset.find(party[i])) {
answer--;
break;
}
}
}
cout << answer;
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
데이터구조 시간에 분리 집합과 관련된 내용이 나왔던 것 같긴 한데 전혀 기억이 안났었다. 덕분에 간만에 복습을 하는 시간이 되었다.
앞으로 한동안은 CLASS 4의 문제들을 위주로 풀고 글을 올리게 될 것 같다. 왜냐하면 CLASS 4 MASTER를 달성하기 위해 풀어야 할 문제들이 너무 많이 남았기 떄문이다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1043